package fun.ticsmyc.question.stringQuestion;

import fun.ticsmyc.tools.ArrayTools;
import org.junit.Test;

/**
 * @author Ticsmyc
 * @package fun.ticsmyc.question.stringQuestion
 * @date 2020-03-08 21:50
 */
public class KMP {

    public static Integer getIndexOf(String str, String match){
        if(str ==null ||match == null || match.length()<1 || str.length()<match.length()){
            return -1;
        }
        char[] s = str.toCharArray();
        char[] m =match.toCharArray();
        int[] next =getNextArray(m);

        int si = 0;
        int mi =0;

        while(si<s.length && mi<m.length){

            if(mi==-1 || s[si]==m[mi]){
                //匹配上了，都后移一位
                si++;
                mi++;
            }else{
                mi=next[mi];
            }
        }

        return mi==m.length? si-mi : -1;
    }

    public static int[] getNextArray(char[] str){
        if (str.length == 1) {
            return new int[]{-1};
        }
        int[] next  = new int[str.length];
        next[0]=-1;
        next[1]=0;

        int cur=2;
        int x=next[cur-1];
        while(cur<str.length){
            if(x==-1 || str[x] == str[cur-1] ){
                next[cur++]=++x;
            }else{
                x=next[x];
            }
        }

        return next;
    }


    @Test
    public void testNext(){
        String str = "abkababkabt";
        int[] next = getNextArray(str.toCharArray());
        ArrayTools.printArray(next);
        //-1  0  0  0  1  2  1  2  3  4  5

    }

    @Test
    public void testNext2(){
        String str = "abcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabc";
        int[] next = getNextArray(str.toCharArray());
        ArrayTools.printArray(next);
        //-1  0  0  0  1  2  1  2  3  4  5

    }

    public static void main(String[] args) {
        String str = "abcabcababaccc";
        String match = "ababa";
//        String str = "et";
//        String match = "et";
        System.out.println(getIndexOf(str, match));
        //6
    }
}
